package link;

/**
 * 单向链表的操作
 */
public class SingleLinkList <T> {

    private Node head;//值不变，next会变
    private int length;

    public SingleLinkList() {
        head = new Node(null, null);
        length = 0;
    }

    /**
     * 是否越界,index在长度内
     */
    private boolean isIndex(int index){
        return index >=0 && index < length;
    }

    /**
     * 是否越界
     */
    private boolean isPos(int index){
        return index >=0 && index <= length;
    }

    /**
     * 检测是否越界
     */
    private void checkIndex(int index){
        if (!isIndex(index)){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.length);
        }
    }

    /**
     * 检测是否越界
     */
    private void checkPos(int index){
        if (!isPos(index)){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.length);
        }
    }

    public Node getHead() {
        return head;
    }

    /**
     * 清空单向链表
     */
    public void clear(){
        head.next = null;
        length = 0;
    }

    /**
     * 判断链表是否为空，是返回true，否返回false
     */
    public boolean isEmpty(){
        return length == 0;
    }

    /**
     * 获取链表中元素的个数
     */
    public int size(){
        return length;
    }

    /**
     * 读取并返回链表中的第index个元素的值
     */
    public Node get(int index){
        checkIndex(index);
        Node pause = head.next;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        return pause;
    }

    /**
     * 返回链表中首次出现的指定的数据元素的位序号
     */
    public int indexOf(T t){
        Node pause = head;
        for (int i=0;i<length;++i){
            pause = pause.next;
            if (pause.data == t){
                return i;
            }
        }
        return -1;
    }

    /**
     * 在链表中添加一个元素
     */
    public void add(T t){
        add(length, t);
    }

    /**
     * 在链表的index插入一个值为t的数据元素
     */
    public void add(int index, T t){
        checkPos(index);
        Node pause = head;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        Node newNode = new Node(t, pause.next);
        pause.next = newNode;
        ++length;
    }

    public void addAll(SingleLinkList list){
        Node pause = head;
        while (pause.next != null){
            pause = pause.next;
        }
        pause.next = list.getHead().next;
    }

    /**
     * 第i个元素替换成一个值为t的数据元素
     */
    public void set(int index, T t){
        checkIndex(index);
        Node pause = head;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        pause.next.data = t;
    }

    /**
     * 删除并返回链表中第i个数据元素
     */
    public T remove(int index){
        checkIndex(index);
        Node pause = head;
        for (int j=0;j<index;++j){
            pause = pause.next;
        }
        Node current = pause.next;
        pause.next = pause.next.next;
        --length;
        return current.data;
    }

    /**
     * 显示链表所有节点的数据
     */
    public String toString(){
        if (isEmpty()){
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        Node pause = head;
        while (pause.next != null){
            pause = pause.next;
            if (!sb.toString().isEmpty()){
                sb.append(',').append(' ');
            }
            sb
                    .append("(")
                    .append(pause.data)
                    .append(",")
                    .append(pause.next==null || pause.next.data==null ? null : pause.next.data)
                    .append(")");
        }
        sb
                .insert(0, "[")
                .append(']');
        return sb.toString();
    }

    /**
     * 节点类
     */
    class Node {
        T data;
        Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}
